package com.Offer;

/*
    面试题47：礼物的最大价值
    在一个m*n的棋盘的每一格都放了一个礼物，每个礼物都有一定的价值，从棋盘的左上角开始，走到棋盘的右下角。
    每次可以向下或者向右，请计算最多拿到多少价值的礼物。

    例如:1 10 3 8
        12 2 9 6
        5 7 4 11
        3 7 16 5
    最大礼物价值为：1+12+5+7+7+16+5 =53
 */
public class demo47 {
    public static void main(String[] args) {
        int[][] values = {{1,10,3,8},{12,2,9,6},{5,7,4,11},{3,7,16,5}};
        System.out.println(getMaxValue_solution(values));
    }

    public static int getMaxValue_solution(int[][] values){
        if (values == null || values.length <= 0 || values[0].length <= 0){
            return 0;
        }

        int[] maxValues = new int[values[0].length];//长度为棋盘的列数
        for(int i = 0;i < values.length;i++){
            for(int j = 0;j < values[0].length;j++){
                int left = 0;
                int up = 0;

                if(i > 0)
                    up = maxValues[j];
                if(j > 0)
                    left = maxValues[j-1];
                //在一个i循环中，每次判断maxValues[i][j]的左边的最大价值和上面的最大价值谁更大,所以我们的数组长度是列数
                maxValues[j] = Math.max(left,up)+values[i][j];

            }
        }
        int maxValue = maxValues[maxValues.length-1];
        return maxValue;
    }

}
